class Solution(object):
    def twoSum(self, nums, target):
	"""
	:type nums: List[int]
	:type target: int
		:rtype: List[int]
	"""
	num2id = {}
	for i in xrange(len(nums)):
		if nums[i] in num2id:
			num2id[nums[i]].append(i)
		else:
			num2id[nums[i]] = [i]

	nums.sort()

 head = 0
	tail = len(nums) - 1
	res = []
	while True:
		if nums[head] + nums[tail] == target:
			res.append(num2id[nums[head]][0])
			if nums[head] == nums[tail]:
				res.append(num2id[nums[head]][1])
			else:
				res.append(num2id[nums[tail]][0])
			break
		elif nums[head] + nums[tail] < target:
			head += 1
		else:
			tail -= 1

	return res